package com.starview.star.operators.relation.runtime;

import java.util.List;

import com.starview.platform.data.EvaluationException;
import com.starview.platform.data.IFunction;
import com.starview.platform.data.IValue;
import com.starview.platform.data.value.Factory;

public class ValueSort
{
  public static List<IValue> quickSort(List<IValue> data, IFunction comparator) throws EvaluationException
  {
    int limit = data.size();

    sort(data, 0, limit, comparator);
    return data;
  }

  private static void sort(List<IValue> data, int from, int limit, IFunction comparator) throws EvaluationException
  {
    if (from < limit) {
      int pivotIx = partition(data, from, limit, (limit + from) / 2, comparator);
      sort(data, from, pivotIx, comparator);
      sort(data, pivotIx + 1, limit, comparator);
    }
  }

  private static int partition(List<IValue> data, int from, int limit, int pivotIx, IFunction comparator)
      throws EvaluationException
  {
    int stIx = from;

    IValue pivot = data.get(pivotIx);
    int end = limit - 1;
    swap(data, pivotIx, end); // move to end

    for (int ix = from; ix < end; ix++) {
      if (Factory.boolValue(comparator.enter(data.get(ix), pivot)))
        swap(data, stIx++, ix);
    }
    swap(data, stIx, end); // put pivot in right place

    return stIx;
  }

  private static <T> void swap(List<T> data, int lft, int rgt)
  {
    if (lft != rgt) {
      T el = data.get(lft);
      data.set(lft, data.get(rgt));
      data.set(rgt, el);
    }
  }
}
